package org.getOffer.offer34;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author yu
 * @Date 2021/10/30
 */
public class Solution {

    List<List<Integer>> listArrayList = new ArrayList<>();

    public static void main(String[] args) {

/*        TreeNode treeNode1 = new TreeNode(7);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(11, treeNode1, treeNode2);
        TreeNode treeNode11 = new TreeNode(13);
        TreeNode treeNode4 = new TreeNode(4, treeNode3, treeNode11);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode6 = new TreeNode(1);
        TreeNode treeNode7 = new TreeNode(4, treeNode5, treeNode6);
        TreeNode treeNode8 = new TreeNode(13);
        TreeNode treeNode9 = new TreeNode(8, treeNode8, treeNode7);
        TreeNode treeNode10 = new TreeNode(5, treeNode4, treeNode9);*/

        TreeNode treeNode1 = new TreeNode();
        TreeNode treeNode2 = new TreeNode(-3);
        TreeNode treeNode3 = new TreeNode(-2);
        treeNode3.right = treeNode2;

        Solution solution = new Solution();
        solution.pathSum(treeNode3, -5);

    }

    public List<List<Integer>> pathSum(TreeNode root, int target) {

        if (root == null) {
            return listArrayList;
        }

        List<Integer> integerList = new ArrayList<>();

        this.recursive(root, target, integerList);

//        for (List<Integer> list : listArrayList) {
//            //Collections.reverse(list);
//            for (Integer i : list) {
//                System.out.print(i);
//            }
//            System.out.println();
//        }

        return listArrayList;
    }

    public void recursive (TreeNode node, int target, List<Integer> integerList) {

        if (node == null) {
            return;
        }
        List<Integer> temp = new ArrayList<>(integerList);
        temp.add(node.val);

        if (node.left != null) {
            this.recursive(node.left, target - node.val, temp);
        }

        if (node.right != null) {
            this.recursive(node.right, target - node.val, temp);
        }

        if (target - node.val == 0 && node.left == null && node.right == null) {
            listArrayList.add(temp);
        }

    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
